module Sort

let rec insert ls n =
  match ls with
  | [] -> [n]
  | x::xs ->
    if n > x then x :: insert xs n
    else n :: ls

let rec insertSort ls =
  List.fold insert [] ls

let test =
  insertSort [1; 7; 8; 9; 3; 4; 5; 10; 6; 2]
  |> printf "%A\n"
